home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1995 April / Internet Tools.iso / infoserv / wais / ir-book-sources / mphf / order.c.Z / order.c
Encoding:
C/C++ Source or Header  |  1993-04-07  |  5.9 KB  |  206 lines
  1. /******************************  order.c  ************************************
  2.  
  3.    Purpose:    Implement the ordering stage of the MPHF algorithm.
  4.  
  5.    Provenance:    Written and tested by Q. Chen and E. Fox, March 1991.
  6.            Edited and tested by S. Wartik, April 1991.
  7.  
  8.    Notes:    None.
  9. **/
  10.  
  11. #include <stdio.h>
  12.  
  13. #include "types.h"
  14. #include "support.h"
  15. #include "vheap.h"
  16.  
  17. #ifdef __STDC__
  18.  
  19. extern void    delete_from_rList( vertexType *vertex, verticesType *vertices );
  20. extern void    append_to_VS( vertexType *vertex, verticesType *vertices );
  21. extern void    initialize_rList( verticesType *vertices );
  22.  
  23. #else
  24.  
  25. extern void    delete_from_rList();
  26. extern void    append_to_VS();
  27. extern void    initialize_rList();
  28.  
  29. #endif
  30.  
  31. /*************************************************************************
  32.  
  33.     ordering( arcs, vertices )
  34.  
  35.   Return:    void
  36.  
  37.   Purpose:    Generate an ordering of the vertices.
  38.  
  39.   Notes:    The ordering of the vertices is a linked list, the head
  40.           of which is in vertices->vsList.  The "next element"
  41.         pointer for each node is in the "succ" field of each
  42.         vertex component.  Note that the "succ" field has two
  43.         purposes in this step.  One is that just mentioned.  The
  44.         other is to be part of the rList used in this step.
  45. **/
  46.  
  47. void ordering( arcs, vertices )
  48.     arcsType        *arcs;     /* in out: the arcs data structure.     */
  49.     verticesType    *vertices; /* in out: the vertices data structure. */
  50. {
  51.     int        degree,
  52.         side;                /* Indicates side of graph.    */
  53.  
  54.     vertexType    *vertex;
  55.     arcType    *arc;
  56.  
  57.     vertices->vsHead = vertices->vsTail = NP;    /* Initialize the VS list. */
  58.  
  59.     initialize_rList( vertices );
  60.     allocate_vheap( arcs->no_arcs, vertices->no_vertices );
  61.  
  62.     while ( vertices->rlistHead != -1 ) {    /* Process each component graph. */
  63.     initialize_vheap();
  64.     vertex = &vertices->vertexArray[vertices->rlistHead];
  65.     do {
  66.         vertex->g = 0;                          /* Mark node "visited".  */
  67.         delete_from_rList( vertex, vertices );
  68.         append_to_VS( vertex, vertices );
  69.         if ( vertex->first_edge != 0 ) {
  70.         /* Add adjacent nodes that are not visited and  */
  71.         /* not in virtual heap to the virtual heap.    */
  72.  
  73.         side = vertex - vertices->vertexArray >= vertices->no_vertices/2;
  74.  
  75.         arc = vertex->first_edge;
  76.         while ( arc != 0 ) {
  77.             int        adj_node;    /* Node adjacent to vertex. */
  78.  
  79.             adj_node = arc->h12[(side+1)%2];
  80.             degree = vertices->vertexArray[adj_node].g;
  81.  
  82.             if ( degree > 0 ) {            /* One such node is found. */
  83.             add_to_vheap( &vertices->vertexArray[adj_node], degree );
  84.             vertices->vertexArray[adj_node].g *= -1;
  85.             }
  86.             arc = arc->next_edge[side];
  87.         }
  88.         }
  89.     } while ( max_degree_vertex( &vertex ) == NORM );
  90.     }
  91.     free_vheap();
  92. }
  93.  
  94.  
  95. /*************************************************************************
  96.  
  97.     delete_from_rList( vertex, vertices )
  98.  
  99.   Return:    void
  100.  
  101.   Purpose:    Delete a vertex pointing at by vertex from the rList stored
  102.         in the vertices data structure.
  103. **/
  104.  
  105. void delete_from_rList( vertex, vertices )
  106.    vertexType    *vertex;        /* in: vertex to delete.       */
  107.    verticesType *vertices;         /* out: vertices data structure. */
  108. {
  109.     if ( vertex->prec != NP )
  110.     vertices->vertexArray[vertex->prec].succ = vertex->succ;
  111.     else
  112.     vertices->rlistHead = vertex->succ;
  113.  
  114.     if ( vertex->succ != NP )
  115.     vertices->vertexArray[vertex->succ].prec = vertex->prec;
  116. }
  117.  
  118.  
  119. /*************************************************************************
  120.  
  121.     append_to_VS( vertex, vertices )
  122.  
  123.   Return:    void
  124.  
  125.   Purpose:    Append the vertex to the vertex ordering VS.
  126. **/
  127.  
  128. void append_to_VS( vertex, vertices )
  129.     vertexType     *vertex;       /* in: the vertex to be added.       */
  130.     verticesType *vertices;        /* out: the vertices data structure. */
  131. {
  132.     int newTail = vertex - vertices->vertexArray;
  133.  
  134.     vertex->succ = vertex->prec = NP;
  135.     if ( vertices->vsHead == NP )
  136.     vertices->vsHead = newTail;
  137.     else
  138.     vertices->vertexArray[vertices->vsTail].succ = newTail;
  139.     vertices->vsTail = newTail;
  140. }
  141.  
  142.  
  143. /*************************************************************************
  144.  
  145.     initialize_rList( vertices )
  146.  
  147.   Return:    void
  148.  
  149.   Purpose:    Set up an rList from the vertices.  An rList is a
  150.         doubly-linked list of vertices in decending order of
  151.         degree.
  152.  
  153.   Notes:    pred and succ are used to store the list.        
  154. **/
  155.  
  156. void initialize_rList( vertices )
  157.     verticesType *vertices;    /* in out: vertices to be ordered.    */
  158. {
  159.     int        i, j, previous;
  160.     intSetType    heads,    /* Two sets of pointers. Element i of "heads" points at    */
  161.         tails;    /* the head of a list about degree i, 0<=i<=maxDegree.    */
  162.                 /* The elements of "tails" are the corresponding tails.    */
  163.  
  164.     heads.count = vertices->maxDegree + 1;
  165.     heads.intSetRep = (int*)owncalloc( heads.count, sizeof(int) );
  166.     for ( i = 0; i < heads.count; i++ )
  167.     heads.intSetRep[i] = NP;
  168.  
  169.     tails.count = vertices->maxDegree + 1;
  170.     tails.intSetRep = (int*) owncalloc( tails.count, sizeof(int) );
  171.     for ( i = 0; i < tails.count; i++ )
  172.     tails.intSetRep[i] = NP;
  173.  
  174.               /* Construct lists for vertices being of */
  175.               /* degree 0, 1, ... maxDegree.           */
  176.     for ( i = 0; i < vertices->no_vertices; i++ ) {
  177.     previous = heads.intSetRep[vertices->vertexArray[i].g];
  178.     vertices->vertexArray[i].succ =  previous;
  179.     if ( previous != NP )
  180.         vertices->vertexArray[previous].prec = i;
  181.     else
  182.         tails.intSetRep[vertices->vertexArray[i].g] = i;
  183.     heads.intSetRep[vertices->vertexArray[i].g] = i;
  184.     vertices->vertexArray[i].prec = NP;
  185.     }
  186.  
  187.     /* Construct the rList by linking lists for vertices being of  */
  188.     /* degree 0, 1, ... maxDegree.                        */
  189.     for ( i = heads.count - 1; i > 1; i-- )
  190.     if ( tails.intSetRep[i] != NP ) {
  191.         for ( j = i - 1; j >= 1; j-- )
  192.         if ( heads.intSetRep[j] != NP )
  193.             break;
  194.         if ( j >= 1 ) {
  195.             vertices->vertexArray[tails.intSetRep[i]].succ =
  196.                 heads.intSetRep[j];
  197.             vertices->vertexArray[heads.intSetRep[j]].prec =
  198.                 tails.intSetRep[i];
  199.         }
  200.     }
  201.     vertices->rlistHead = heads.intSetRep[vertices-> maxDegree];
  202.  
  203.     free( (char *)heads.intSetRep );
  204.     free( (char *)tails.intSetRep );
  205. }
  206.